
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) return nullptr;
        TreeNode* left = invertTree(root->left);
        TreeNode* right = invertTree(root->right);
        root->left = right;
        root->right = left;
        return root;





    }
};
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>>dp(m + 1, vector<int>(n + 1, 0));
        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; i++)
        {
            dp[i][0] = dp[i - 1][0] + grid[i][0];

        }
        for (int i = 1; i < n; i++)
        {
            dp[0][i] = dp[0][i - 1] + grid[0][i];

        }
        for (int i = 1; i < m; i++)
        {
            for (int j = 1; j < n; j++)
            {
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
                //cout<<dp[i][j]<<" ";
            }
            //cout<<endl;
        }

        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                // dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];
                cout << dp[i][j] << " ";
            }
            cout << endl;
        }












        return dp[m - 1][n - 1];
        // return 0;

    }
}; class Solution {
public:
    bool isValid(string s) {

        stack<char>st;
        for (auto e : s)
        {

            if (e == '(' || e == '[' || e == '{')
            {
                st.push(e);
            }
            else
            {

                if (st.empty())return false;




                else if (st.top() == '(' && e == ')' || st.top() == '[' && e == ']' || st.top() == '{' && e == '}')
                {

                    st.pop();


                }
                else
                {
                    return false;
                }


            }
        }

        return st.empty();





    }
}; class Solution {
public:
    int maxSubArray(vector<int>& nums) {

        int m = nums.size();
        vector<int>dp(m);
        dp[0] = nums[0];
        cout << dp[0] << " ";
        for (int i = 1; i < m; i++)
        {

            dp[i] = max(dp[i - 1] + nums[i], nums[i]);
            cout << dp[i] << " ";

        }

        int maxp = INT_MIN;
        for (int i = 0; i < m; i++)
        {
            maxp = max(maxp, dp[i]);



        }
        return maxp;






    }
}; class Solution {
public:
    vector<vector<string>>  result;
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>>st;
        for (auto str : strs)
        {
            string strr = str;
            sort(str.begin(), str.end());
            st[str].push_back(strr);

        }
        for (auto e : st)
        {
            result.push_back(e.second);
        }


        return result;

    }
}; class Solution {
public:



    void moveZeroes(vector<int>& nums) {
        int left = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            if (nums[i] != 0)
            {
                nums[left] = nums[i];
                left++;
            }
        }
        for (int i = left; i < nums.size(); i++)
        {

            nums[i] = 0;




        }
    }
}; class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int m = nums.size();
        if (m == 0)return 0;
        int maxp = 1;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < m;)
        {
            int j = i + 1, count = 1;
            while (j < m)
            {
                if (nums[j] == nums[j - 1] + 1)
                {
                    count++;
                    maxp = max(maxp, count);
                    j++;
                }
                else if (nums[j] == nums[j - 1])
                {
                    j++;
                }
                else
                {
                    break;
                }

            }

            i = j;
        }

        return maxp;





    }
}; class Solution {
public:
    void reserve(vector<int>& nums, int left, int right)
    {
        while (left < right)
        {
            int tmp = nums[left];
            nums[left] = nums[right];
            nums[right] = tmp;
            left++;
            right--;
        }


    }
    void rotate(vector<int>& nums, int k) {
        int m = nums.size();
        if (k > m)k %= m;
        reserve(nums, 0, nums.size() - 1);
        reserve(nums, 0, k - 1);
        reserve(nums, k, nums.size() - 1);


    }
}; class Solution {
public:
    vector<vector<int>> result;
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        result.push_back(intervals[0]);
        for (int i = 1; i < intervals.size(); i++)
        {
            if (intervals[i][0] <= result.back()[1])
            {

                result.back()[1] = max(result.back()[1], intervals[i][1]);
            }
            else
            {
                result.push_back(intervals[i]);
            }

        }
        return result;
    }
};